package com.company;

/**
 * @author zhf
 * @date 2021/10/19
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 */
public class CreateBracket {

    public static void main(String[] args) {
        int n = 10;
        CreateBracket createBracket = new CreateBracket();
        List<String> ans = createBracket.generateParenthesis(n);
        System.out.println(ans);
    }


    List<String> ans = new ArrayList<String>();

    public List<String> generateParenthesis(int n) {
        /*
        刚开始左右括号的数量都为0；
         */
        dfs(0,0,n,"");
        return ans;
    }

    /**
     *深度优先遍历
     * @param left  左括号数量；
     * @param right  右括号数量；
     * @param n  初始化定义括号对数量；
     * @param str  当前合法的括号数量；
     */
    public void dfs(int left,int right,int n,String str){
        if (left == n && right ==n) {
            ans.add(str);
        }

        else {

            if (left < n) {
                dfs(left+1,right,n,str+"(");  //递归，如果左括号的数量比初始化规定的少，则填入左括号；
            }

            if (right < left && right < n) {
                dfs(left,right+1,n,str+")"); //递归，如果右括号的数量比左括号少并且比规定的少，则填入右括号
            }

        }

    }
}
